next_permutation

std::next_permutation 是 C++ 标准库中的一个函数，用于生成给定序列的下一个字典序排列。如果可能，它会重新排列序列中的元素，形成下一个更大的排列，并返回 true。如果这个序列已经是最大的排列，则将其重置为最小的排列（即升序排列），并返回 false。这个函数定义在 <algorithm> 头文件中。

基本用法

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

• first 和 last 是双向迭代器，分别指向序列的开始和结束。

示例

对 std::vector 使用 next_permutation

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3};

    std::cout << "{1, 2, 3}的全排列为：\n";
    do {
        for (int num : vec) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation(vec.begin(), vec.end()));

    return 0;
}

/*
{1, 2, 3}的全排列为：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/

这段代码会打印出 {1, 2, 3} 的所有排列。

对字符串使用 next_permutation

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    std::string str = "abc";

    std::cout << "\"abc\" 的全排列为：\n";
    do {
        std::cout << str << "\n";
    } while (std::next_permutation(str.begin(), str.end()));

    return 0;
}

/*
"abc" 的全排列为：
abc
acb
bac
bca
cab
cba
*/

这段代码会打印出 "abc" 的所有排列。

注意事项

• 在第一次调用 next_permutation 前，序列应该处于想要开始的排列顺序。

  如果你希望遍历所有可能的排列，确保序列是按字典序最小（即升序）排列的。

• next_permutation 不仅可以用于数字的排列，还可以用于任何支持比较操作的元素类型的序列，包括字符、字符串等。

• 这个函数在使用时不需要额外的存储空间，它直接在原地修改序列。

std::next_permutation 是一个非常实用的工具，能够帮助解决排列组合相关的问题，比如寻找字典序的下一个排列、遍历一个集合的所有排列等。由于它的实现考虑了字典序的规则，因此可以有效地用于算法竞赛、问题求解等场景。

⬅️ isalpha-isdigit 🏠 00-刷题理模型 ➡️ ascii基础 getline